from __future__ import with_statement
import os
from bisect import bisect_left as bisect
import string
import itertools

class Dictionary(object):
	def checkWord(self,word):
		pass
	def checkPrefix(self,prefix):
		pass

class SimpleDictionary(object):
	def __init__(self,words,allow_proper_names=False,pre_index_snippets=False,debug=False):

		self.debug = debug
		if debug: print 'Initializing %s word dictionary%s...' \
			% (len(words),' (ignoring proper names)' if not allow_proper_names else '')

		if allow_proper_names:
			self.dictionaryList = words
		else:	
			self.dictionaryList = [x for x in words if x[0].upper() != x[0]]

		self.dictionaryList.sort()
		self.dictionarySet = set(self.dictionaryList)
		
		self.dictionaryReversed = []
		
		self.dictionarySnippets = {}
		if pre_index_snippets:
			self.__index_snippets()
	
	def __index_reversed(self):
		for word in self.dictionaryList:
			self.dictionaryReversed.append(reverse(word))
		self.dictionaryReversed.sort()
	
	def __index_snippets(self):	
		if self.debug: print 'Initializing snippet index...'
		
		for word in self.dictionaryList:
			for length in xrange(2,len(word)-1):
				for i in xrange(0,len(word)-length):
					snippet = word[i:i+length]
					if self.dictionarySnippets.get(snippet):
						self.dictionarySnippets[snippet].append(word)
					else:
						self.dictionarySnippets[snippet] = [word]
		
	def __len__(self):
		return len(self.dictionarySet)

	def checkWord(self,word):
		return ''.join(word) in self.dictionarySet
	
	def checkPrefix(self,prefix):
		""" Return None if the prefix is not found in the dictionary
		otherwise return the first word matched (there may be other words
		which match this prefix)."""
		with_prefix = []
		ins_point = bisect(self.dictionaryList,''.join(prefix))
		try:
			if self.dictionaryList[ins_point].startswith(''.join(prefix)):
				with_prefix.append(self.dictionaryList[ins_point])
			for c in itertools.count(1):
				a = b = False
				if self.dictionaryList[ins_point+c].startswith(''.join(prefix)):
					with_prefix.append(self.dictionaryList[ins_point+c])
					a = True
				if self.dictionaryList[ins_point-c].startswith(''.join(prefix)):
					with_prefix.append(self.dictionaryList[ins_point-c])
					b = True
				if not a and not b: break
		except IndexError:
			pass
		return with_prefix


	def checkSuffix(self,suffix):
		if not self.dictionaryReversed:
			self.__index_reversed()
		s = reverse(suffix)
		with_suffix = []
		ins_point = bisect(self.dictionaryReversed,''.join(s))
		try:
			if self.dictionaryReversed[ins_point].startswith(''.join(s)):
				with_suffix.append(self.dictionaryReversed[ins_point])
			for c in itertools.count(1):
				a = b = False
				if self.dictionaryReversed[ins_point+c].startswith(''.join(s)):
					with_suffix.append(self.dictionaryReversed[ins_point+c])
					a = True
				if self.dictionaryReversed[ins_point-c].startswith(''.join(s)):
					with_suffix.append(self.dictionaryReversed[ins_point-c])
					b = True
				if not a and not b: break
		except IndexError:
			pass
			
		return [reverse(x) for x in with_suffix]
	
	def checkSnippet(self,snippet):
		""" Return a list of words which contain this snippet of characters;
		if chars is not part of any word return an empty list.
		
		If snippet length is less than 2, raise a ValueError.
		"""
		if not self.dictionarySnippets:
			self.__index_snippets()
		if len(snippet) <= 1:
			raise ValueError,"Snippet must be of at least length 2"
			
		return self.dictionarySnippets.get(snippet,[])
		
	
	def dump(self):
		print self.dictionaryList

	@staticmethod
	def fromFile(filename,**kwargs):
		if kwargs.get('debug'): print "Initializing from file %s" % filename
		
		lines = []
		with open(filename,'r') as dictFile:
			for line in dictFile:
				lines.append(line[0:-1])
		return SimpleDictionary(lines,**kwargs)

	@staticmethod
	def load(**kwargs):
		return SimpleDictionary.fromFile("/usr/share/dict/words",**kwargs)

def reverse(s):
	l = list(s)
	l.reverse()
	return ''.join(l)